#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int comp(const void* a, const void* b) {
    return *(int*) a - *(int*) b;
}

int majorityElement1(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), comp);
    return nums[numsSize / 2];
}

int majorityElement(int* nums, int numsSize) {
    int res = nums[0];
    int count = 1;
    for (int i = 1; i < numsSize; i++) {
        if (count == 0) {
            res = nums[i];
            count++;
        } else {
            if (res == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
    }
    return res;
}

int main() {
    int nums[] = { 1, 2, 3, 2, 4, 2, 2 };
    int res = majorityElement(nums, sizeof(nums) / sizeof(int));
    printf("res = %d\n", res);
    return 0;
}
